package com.ting.test.algorithms.大厂刷题班;

import java.util.ArrayList;
import java.util.List;

/**
 * 给出一个二维数组,每个子数组有两个值
 * {
 * {1,2}
 * {1,3}
 * {2,7}
 * {8,10}
 * {11,19}
 * {11,13}
 * }
 * 合并后为
 * {
 * {1,7}
 * {8,10}
 * {11,19}
 * }
 */
public class 合并区间 {
    public static void main(String[] args) {
        int[][] arr = new int[][]{{1, 2}, {1, 3}};

        int[][] es = process(arr);


    }

    private static int[][] process(int[][] arr) {
        if (arr == null || arr.length == 1) {
            return arr;
        }

        List<Range> list = new ArrayList<>();
        Range range = new Range(arr[0][0], arr[0][1]);
        for (int i = 1; i < arr.length; i++) {
            //当下一个数组的start大于当前的end时，表明需要重新创建一个range
            if(arr[i][0]> range.start){
                list.add(range);
                range=new Range(arr[i][0], arr[i][1]);
            }
            if(arr[i][0]< range.start){
                range.start=arr[i][0];
            }
            if(arr[i][1]> range.end){
                range.end=arr[i][1];
            }
        }

        int [][] result=new int[list.size()][2];
        for(int i=0;i<list.size();i++){
            result[i][0]=list.get(i).start;
            result[i][1]=list.get(i).end;

        }


        return result;
    }

    public static class Range {
        int start;
        int end;

        public Range(int start, int end) {
            this.start = start;
            this.end = end;
        }
    }
}
